{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Adjacent Swaps for K Consecutive Ones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minMoves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得到连续 K 个 1 的最少相邻交换次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> 。 <code>nums</code> 仅包含 <code>0</code> 和 <code>1</code> 。每一次移动，你可以选择 <strong>相邻</strong> 两个数字并将它们交换。</p>\n",
    "\n",
    "<p>请你返回使 <code>nums</code> 中包含 <code>k</code> 个 <strong>连续 </strong><code>1</code> 的 <strong>最少</strong> 交换次数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,0,0,1,0,1], k = 2\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>在第一次操作时，nums 可以变成 [1,0,0,0,<strong>1</strong>,<strong>1</strong>] 得到连续两个 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,0,0,0,0,0,1,1], k = 3\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,<strong>1</strong>,<strong>1</strong>,<strong>1</strong>] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,1,0,1], k = 2\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>nums 已经有连续 2 个 1 了。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums[i]</code> 要么是 <code>0</code> ，要么是 <code>1</code> 。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= sum(nums)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-adjacent-swaps-for-k-consecutive-ones](https://leetcode.cn/problems/minimum-adjacent-swaps-for-k-consecutive-ones/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-adjacent-swaps-for-k-consecutive-ones](https://leetcode.cn/problems/minimum-adjacent-swaps-for-k-consecutive-ones/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,0,1,0,1]\\n2', '[1,0,0,0,0,0,1,1]\\n3', '[1,1,0,1]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# let i0, i1, .., ik-1 be indices of k consecutive ones\r\n",
    "# groupping them towards an index i0 <= i <= ik-1, requires\r\n",
    "#   i - ij-1 + i - 1 - ij-1 + .. + i - (j - 1) - i0\r\n",
    "# + ij - i + ij+1 - i - 1 + .. + ik-1 - i - (k - j - 1)\r\n",
    "# moves, where ij-1 < i <= ij\r\n",
    "# = j * i - sum(i0 .. ij-1) - (j - 1) * j / 2\r\n",
    "# - (k - j) * i + sum(ij .. ik-1) - (k - j - 1) * (k - j) / 2\r\n",
    "# = (2j - k) * i + sum(ij .. ik-1) - sum(i0 .. ij-1) - (2jj + kk - 2kj - k) / 2\r\n",
    "# to minimize the moves, j = k // 2\r\n",
    "from collections import deque\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\r\n",
    "        res = float('inf')\r\n",
    "        n = len(nums)\r\n",
    "        halfK = k // 2\r\n",
    "        first: deque[int] = deque()\r\n",
    "        second: deque[int] = deque()\r\n",
    "        sumDiff = 0 # second sum - first sum\r\n",
    "        const1 = halfK + (halfK * (halfK - 1) + (k - halfK - 1) * (k - halfK)) // 2\r\n",
    "        const2 = 2 * halfK - k\r\n",
    "        for i in range(n):\r\n",
    "            if nums[i] == 0: continue\r\n",
    "            second.append(i)\r\n",
    "            sumDiff += i\r\n",
    "            while len(second) > k - halfK:\r\n",
    "                sumDiff -= 2 * second[0]\r\n",
    "                first.append(second.popleft())\r\n",
    "            while len(first) > halfK:\r\n",
    "                sumDiff += first.popleft()\r\n",
    "            \r\n",
    "            if len(first) == halfK:\r\n",
    "                res = min(res, const2 * second[0] + sumDiff - const1)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# let i0, i1, .., ik-1 be indices of k consecutive ones\r\n",
    "# groupping them towards an index i0 <= i <= ik-1, requires\r\n",
    "#   i - ij-1 + i - 1 - ij-1 + .. + i - (j - 1) - i0\r\n",
    "# + ij - i + ij+1 - i - 1 + .. + ik-1 - i - (k - j - 1)\r\n",
    "# moves, where ij-1 < i <= ij\r\n",
    "# = j * i - sum(i0 .. ij-1) - (j - 1) * j / 2\r\n",
    "# - (k - j) * i + sum(ij .. ik-1) - (k - j - 1) * (k - j) / 2\r\n",
    "# = (2j - k) * i + sum(ij .. ik-1) - sum(i0 .. ij-1) - (2jj + kk - 2kj - k) / 2\r\n",
    "# to minimize the moves, j = k // 2\r\n",
    "from collections import deque\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\r\n",
    "        res = -1\r\n",
    "        n = len(nums)\r\n",
    "        halfK = k // 2\r\n",
    "        first: deque[int] = deque()\r\n",
    "        second: deque[int] = deque()\r\n",
    "        fsum = ssum = 0\r\n",
    "        for i in range(n):\r\n",
    "            if nums[i] == 0: continue\r\n",
    "            second.append(i)\r\n",
    "            ssum += i\r\n",
    "            while len(second) > k - halfK:\r\n",
    "                ssum -= second[0]\r\n",
    "                fsum += second[0]\r\n",
    "                first.append(second.popleft())\r\n",
    "            while len(first) > halfK:\r\n",
    "                fsum -= first.popleft()\r\n",
    "            \r\n",
    "            if len(first) == halfK:\r\n",
    "                res = min(res,\r\n",
    "                    halfK * (second[0] - 1) - fsum - halfK * (halfK - 1) // 2\r\n",
    "                        - (k - halfK) * second[0] + ssum - (k - halfK - 1) * (k - halfK) // 2,\r\n",
    "                    key=lambda x: x if x != -1 else float('inf')\r\n",
    "                    )\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        zeros = self.generate_zeros(nums)\n",
    "        add_sum = list(accumulate(zeros, initial=0))\n",
    "        cost = 0\n",
    "        for i in range(k-1):\n",
    "            cost += zeros[i] * min(i+1, k-1-i)\n",
    "        min_cost = cost\n",
    "        for i in range(1,len(zeros)-k+2):\n",
    "            left,right = i,i+k-2\n",
    "            mid = (left+right)//2\n",
    "            cost -= (add_sum[mid]-add_sum[i-1])\n",
    "            cost += (add_sum[right+1]-add_sum[mid+k%2])\n",
    "            min_cost = min(min_cost, cost)\n",
    "        return min_cost\n",
    "    \n",
    "    def generate_zeros(self, nums:List[int]):\n",
    "        zero = []\n",
    "        cnt = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                zero.append(cnt)\n",
    "                cnt = 0\n",
    "        return zero[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        m = 0\n",
    "        for i, p in enumerate(i for i, x in enumerate(nums) if x):\n",
    "            nums[i] = p - i\n",
    "            m += 1\n",
    "        if m == len(nums): return 0  # 全部都是 1\n",
    "        ans, p = inf, nums\n",
    "        sl, sm, sr = 0, sum(p[:k // 2]), sum(p[:k])  # s[i] s[i+k//2] s[i+k] 忽略切片开销\n",
    "        for i in range(m - k + 1):\n",
    "            ans = min(ans, sl + sr - sm * 2 - p[i + k // 2] * (k % 2))\n",
    "            sl += p[i]\n",
    "            sm += p[i + k // 2]\n",
    "            sr += p[i + k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        m = 0\n",
    "        for i, p in enumerate(i for i, x in enumerate(nums) if x):\n",
    "            nums[i] = p - i\n",
    "            m += 1\n",
    "        if m == len(nums): return 0  # 全部都是 1\n",
    "        ans, p = inf, nums\n",
    "        sl, sm, sr = 0, sum(p[:k // 2]), sum(p[:k])  # s[i] s[i+k//2] s[i+k] 忽略切片开销\n",
    "        for i in range(m - k + 1):\n",
    "            ans = min(ans, sl + sr - sm * 2 - p[i + k // 2] * (k % 2))\n",
    "            sl += p[i]\n",
    "            sm += p[i + k // 2]\n",
    "            sr += p[i + k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        m = 0\n",
    "        for i, p in enumerate(i for i, x in enumerate(nums) if x):\n",
    "            nums[i] = p - i\n",
    "            m += 1\n",
    "        if m == len(nums): return 0  # 如果数组中的所有元素都是 1，则不需要任何交换\n",
    "        ans, p = inf, nums\n",
    "        sl, sm, sr = 0, sum(p[:k // 2]), sum(p[:k])  # 计算前k个1的位置之间的距离\n",
    "        for i in range(m - k + 1):\n",
    "            ans = min(ans, sl + sr - sm * 2 - p[i + k // 2] * (k % 2))\n",
    "            sl += p[i]\n",
    "            sm += p[i + k // 2]\n",
    "            sr += p[i + k]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        idxs=[i for i,v in enumerate(nums) if v==1]\n",
    "        cur=sum(abs(idxs[i]-idxs[k//2])-abs(i-k//2) for i in range(k))\n",
    "        res=cur\n",
    "        for i in range(k,len(idxs)):\n",
    "            midIdxIdx=i-k+k//2\n",
    "            cur-=idxs[midIdxIdx]-idxs[i-k]-(midIdxIdx-(i-k)) # pop最左边的元素\n",
    "            midIdxIdx=i-k+1+(k-1)//2\n",
    "            cur+=idxs[i]-idxs[midIdxIdx]-(i-midIdxIdx) # append到最右边\n",
    "            res=min(res,cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        a=[]\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]!=0:a.append(i-len(a))\n",
    "        m=len(a)\n",
    "        s=[0]*(m+1)\n",
    "        for i in range(m):s[i+1]=s[i]+a[i]\n",
    "        mn=math.inf\n",
    "        for i in range(m-k+1):mn=min(mn,s[i+k]+s[i]-s[i+k//2]*2-a[i+k//2]*(k&1))\n",
    "        return mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        a=[]\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]!=0:a.append(i-len(a))\n",
    "        m=len(a)\n",
    "        s=[0]*(m+1)\n",
    "        for i in range(m):s[i+1]=s[i]+a[i]\n",
    "        mn=math.inf\n",
    "        for i in range(m-k+1):\n",
    "            mn=min(mn,s[i+k]+s[i]-s[i+k//2]*2-a[i+k//2]*(k&1))\n",
    "        return mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        p=[q-i for i,q in enumerate(i for i,x in enumerate(nums) if x)]\n",
    "        s=list(accumulate(p, initial=0))\n",
    "        return min(s[i]+s[i+k]-s[i+k//2]*2-p[i+k//2]*(k&1) for i in range(len(p)-k+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        p=[]\n",
    "        for i,x in enumerate(nums):\n",
    "            if x!=0:\n",
    "                p.append(i-len(p))\n",
    "        n=len(p)\n",
    "        s=list(accumulate(p,initial=0))\n",
    "        ans=inf\n",
    "        for i,x in enumerate(s[:n-k+1]):\n",
    "            ans=min(ans,x+s[i+k]-s[i+k//2]*2-p[i+k//2]*(k%2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        #前缀和的下标相减\n",
    "        p = []\n",
    "        \n",
    "        for i,x in enumerate(nums):\n",
    "            if x == 1:\n",
    "                p.append(i)\n",
    "\n",
    "        for j,i in enumerate(p):\n",
    "            p[j] = i - j\n",
    "\n",
    "        s = list(accumulate(p,initial = 0))\n",
    "        ans = inf\n",
    "        for i in range(len(p)-k+1):\n",
    "            ans = min(ans,s[i]+s[i+k]-2*s[i+k//2]-p[i+k//2]*(k%2))\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        p=[q-i for i,q in enumerate(i for i,x in enumerate(nums) if x)]\n",
    "        s=list(accumulate(p, initial=0))\n",
    "        return min(s[i]+s[i+k]-s[i+k//2]*2-p[i+k//2]*(k&1) for i in range(len(p)-k+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        points = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                points.append(i - len(points))\n",
    "        presum = [0]\n",
    "        for p in points:\n",
    "            presum.append(presum[-1] + p)\n",
    "        res = float('inf')\n",
    "        for i in range(len(points) - k + 1):\n",
    "            mid = (i + i + k - 1) // 2 \n",
    "            median = points[mid]\n",
    "            res = min(res, (mid - i) * median - presum[mid] + presum[i] + presum[i + k] - presum[mid + 1] -  (i + k - 1 - mid) * median)\n",
    "        return res\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        # p_list = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] == 0:\n",
    "        #         continue\n",
    "        #     p_list.append(i)\n",
    "        g_list, preSum = [], [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                g_list.append(i-len(g_list))\n",
    "                preSum.append(preSum[-1] + g_list[-1])\n",
    "\n",
    "        res = float('inf')\n",
    "        mid = k//2\n",
    "        for i in range(len(g_list)-k+1):\n",
    "            mid = i + k//2\n",
    "            r = g_list[mid]\n",
    "            value = r*(1-k%2) + (preSum[i+k]-preSum[mid+1]) - (preSum[mid]-preSum[i])\n",
    "            res = min(res, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        g, preSum = [], [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                g.append(i - len(g))\n",
    "                preSum.append(preSum[-1] + g[-1])\n",
    "        m, res = len(g), inf\n",
    "        for i in range(m - k + 1):\n",
    "            mid = i + k // 2\n",
    "            r = g[mid]\n",
    "            res = min(res, (1 - k % 2) * r + (preSum[i + k] - preSum[mid + 1]) - (preSum[mid] - preSum[i]))\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        g, preSum = [], [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                g.append(i - len(g))\n",
    "                preSum.append(preSum[-1] + g[-1])\n",
    "        m, res = len(g), inf\n",
    "        for i in range(m - k + 1):\n",
    "            mid = i + k // 2\n",
    "            r = g[mid]\n",
    "            res = min(res, (1 - k % 2) * r + (preSum[i + k] - preSum[mid + 1]) - (preSum[mid] - preSum[i]))\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        g, preSum = [], [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                g.append(i - len(g))\n",
    "                preSum.append(preSum[-1] + g[-1])\n",
    "        m, res = len(g), inf\n",
    "        for i in range(m - k + 1):\n",
    "            mid = i + k // 2\n",
    "            r = g[mid]\n",
    "            res = min(res, (1 - k % 2) * r + (preSum[i + k] - preSum[mid + 1]) - (preSum[mid] - preSum[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        ind = [i for i in range(n) if nums[i]]\n",
    "        m = len(ind)\n",
    "        pre= list(accumulate(ind, initial=0))\n",
    "        for i in range(m-k+1):\n",
    "            start = ind[i]\n",
    "            end = ind[i+k-1]\n",
    "            mid = ind[i+(k-1)//2]\n",
    "            \n",
    "            left_cnt = (k-1)//2+1\n",
    "            right_cnt = k-left_cnt\n",
    "            cur = (mid+mid-left_cnt+1)*left_cnt//2  - (pre[i+(k-1)//2+1]-pre[i])\n",
    "            cur += (pre[i+k-1+1]-pre[i+(k-1)//2+1])-(mid+1+mid+right_cnt)*right_cnt//2 \n",
    "            if cur < ans:\n",
    "                ans = cur\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
